{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于给定线性表，如果按照题意标准可以把表中连续子串分为两类\n",
    "不妨将符合题意的子串认为真，不符合题意的子串认为假"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "线性表中连续子串中数据增长时会出现两种趋势"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一种是在数据增长时子串的判断趋于真\n",
    "能推出数据很大时子串一定为真，没有数据时子串一定为假\n",
    "所以我们对于最小多少长度的子串判断可以为真感兴趣"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一种是在数据增长时子串的判断趋于假\n",
    "能推出数据很大时子串一定为假，没有数据时子串一定为真\n",
    "所以我们对于最大多少长度的子串判断可以为真感兴趣"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Window:\n",
    "    from collections import deque\n",
    "\n",
    "    def __init__(self):\n",
    "        self.queue = self.deque()\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.queue)\n",
    "\n",
    "    def push(self, x):\n",
    "        self.queue.append(x)\n",
    "\n",
    "\n",
    "    def pop(self):\n",
    "        head = self.queue.popleft()\n",
    "\n",
    "\n",
    "    def true(self):\n",
    "\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LongestSub(l):\n",
    "    window = Window()\n",
    "\n",
    "    M = 0\n",
    "    for i in l:\n",
    "        window.push(i)                  # 初始时为真，只有判断为真的时候才会加入新元素，目的是越长越好\n",
    "\n",
    "        while not window.true():        # 判断为假时不断弹出队列头元素，直到判断为真\n",
    "            window.pop()\n",
    "\n",
    "        M = max(M, len(window))         # 在判断为真时更新最大值\n",
    "\n",
    "    return M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ShortestSub(l):\n",
    "    window = Window()\n",
    "\n",
    "    m = float('inf')\n",
    "    for i in l:\n",
    "        window.push(i)                  # 初始时为假, 只有判断为假的时候才会加入新元素，目的是越短越好\n",
    "\n",
    "        while window.true():            # 判断为真时不断更新最小值，弹出队列头元素，直到判断为假\n",
    "            m = min(m, len(window))     \n",
    "\n",
    "            window.pop()\n",
    "\n",
    "    return m                            # 注意是否存在窗口为真的情况"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.12 (main, Apr  4 2022, 05:22:27) [MSC v.1916 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "3a176caed2e623e3a36a87b094ae4f1cc68623d3a88a2d36a2ea84f7c5d7277a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
